1. Field of the Invention
The invention relates generally to image processing devices such as, for example, printers, scanners, cameras, digitizers, film writers, photo-CD players, general purpose work stations and the like, and image processing systems that include a plurality of image processing devices, which process image data utilizing one or more N to M-dimensional transforms, where N and M are integers each greater than or equal to one.
More particularly, the invention relates to image processing devices and systems which attach stored compressed look-up table (LUT) representations of the aforementioned transforms (or alternatively, some other type of compressed transform representative data), to image data; and to image processing devices and systems which are capable of processing image data that has compressed transform representative data attached thereto.
In the course of explaining the principles of the invention, the more general term "transform representative data" will sometimes be used, as opposed to the more specific references to compressed "transform representative look-up tables" (LUTs). It should be understood that whenever reference is made to look-up tables, a reference to the more general concept of "transform representative data" is intended to be implied.
In accordance with one aspect of the invention, each LUT in a set of LUTs (where each LUT represents an N TO M-dimensional transform which could be applied to the input data), is stored in compressed form in storage means included in, or which is otherwise accessible to, the image processing device or system. Each stored compressed LUT may then, according to one embodiment of the invention, be selectively attached (appended) to the image data being processed by the image processing device or system.
According to a further aspect of the invention, image data which has compressed transform representative data attached thereto (such as one of the aforementioned compressed transform representative LUTs), may be processed utilizing methods and apparatus operative to: (a) detach the compressed LUT from the image data; (b) decompress the detached LUT (if not otherwise available in decompressed form to transform processing means being utilized to process the image data); (c) decompress the image data (if presented to the image processing device or system in compressed form); and (d) apply the transform represented by the decompressed LUT, utilizing the aforementioned transform processing means, to a decompressed version of the image data. The result of the aforementioned process is for the transform processing means to have available as output, image data transformed in accordance with the transform represented by the compressed LUT previously attached to the image data.
2. Description of the Prior Art
Well known methods and apparatus exist for transforming, with the aid of an image processor, one data representation of an image into another representation of the image within image processing devices and systems. One class of transform which may be applied by an image processor to input image data is referred to herein as "N to M dimensional" transforms, where N and M are integers greater than or equal to 1.
When N and M both equal one, the transform is said to be "one dimensional". An example of a one dimensional transform is a simple tonal re-mapping of monochrome imagery. Otherwise the transform is referred to in the art as being "multi-dimensional". An example of a multi-dimensional transform is a mapping that converts color imagery from one color representation into some other representation.
A specific example of a multi-dimensional transform, presented for the sake of illustration only, is a mapping from a Red, Green Blue (RGB) three color space representation of image data, into a Cyan, Magenta, Yellow, Black (CMYK) four color space representation of the same image data. For the aforementioned transform, N equals 3 and M equals 4.
Other examples of multi-dimensional transforms, together with an indication of specific device environments in which they may be applied, include transforms which take red, green and blue (RGB) response signals from an input scanner and convert the data into the CIE tri-stimulus values (XYZ), and transforms which convert CIELAB image data into cyan, magenta, yellow, and black (CMYK) drive signals for an output printer.
It is well known by those skilled in the art that the aforementioned N to M-dimensional transforms may be implemented using look-up tables (LUTs). For example, an image processor could access the contents of a selected LUT in a prescribed manner (e.g., using image data input into an image processing device or system as an index to the LUT), and output a value stored in the LUT to effectively perform the desired data transformation.
Many image processing devices and systems are also known which utilize data compression techniques to reduce memory requirements and increase process throughput. However, the data compression techniques used in such devices and systems are generally applied only to the actual data being processed (for example, the input image data itself); not to the LUTs used to perform desired data transformation processes.
In other known image processing devices and systems, data compression techniques have been used for purposes unrelated to image processing per se. An example is the video signal processor taught by Yamashita in Japanese Patent Number 61-090575, where data compression is used to perform a LUT conversion process.
In a copending U.S. patent application entitled "Methods and Apparatus for Processing Image Data Utilizing Stored Compressed Look-Up Table (LUT) Representations of N to M Dimensional Transforms", filed on Dec. 31, 1992, assigned to the same assignee as the present invention), methods and apparatus are described for utilizing stored compressed N to M dimensional transform representative LUTs for image processing purposes.
The copending application, hereby incorporated by reference, teaches (for example) the use of stored compressed LUTs to perform device calibration functions, transformations between image data spaces recognized by different devices, etc., by selectively decompressing and applying the transform represented by a given compressed LUT, stored in memory accessible to a transform processor, to the image data being processed.
With the exception of the teachings set forth in the aforementioned incorporated patent application, all of the known image processing devices and systems that utilize LUT representations of N to M-dimensional transforms, store the LUTs in an uncompressed form. As a result, the number of LUTs that are capable of being stored may be subject to image processing device or system dependent memory constraints. The incorporated patent application solves this problem and, among other features, allows a broader range of "follow on" devices (such as different types of output printers, display devices, etc.) to be supported by the image processing device or system performing the transforms.
However, the incorporated application does not address methods and apparatus for selectively attaching a stored compressed LUT to image data and/or being able to utilize image data (whether compressed or uncompressed), with compressed transform representative data attached thereto, for image processing purposes, such as, for example, device calibration, image data space transformation, etc.
It would be desirable to be able to provide methods and apparatus for selectively attaching a stored compressed LUT to image data since, for example, an image data file with an attached "transform", could be created and sent as a package to another image processing device or system. The other device or system would only need to be able to detach and reconstruct the transform to be applied to the image data in the file. Accordingly, only the process used to compress the transform representative data would need to be known by the target device or system; and no further information regarding the transform per se would need to be known or stored at the target.
Given the ability to selectively attach a stored compressed LUT to image data, it would clearly be desirable to provide methods and apparatus for being able to utilize image data with compressed transform representative data attached thereto, for image processing purposes such those described hereinabove.
In addition to the aforementioned incorporated patent application (including prior art referred to therein), and the above referenced Yamashita patent, other recently issued patents illustrate the state of the relevant art of imaging systems which use transform representative LUTs and/or data compression techniques for image processing purposes.
These include, U.S. Pat. No. 5,067,019 to Juday et al.; U.S. Pat. No. 4,914,508, to Music et al.; U.S. Pat. No. 4,797,729, to Tsai; U.S. Pat. No. 4,941,038, to Walowit; Japanese Patent Number 63-164574, to Kawamura; Japanese Patent Number 2-237269, to Murakami; Japanese Patent Number 1-51889, to Yamashita; Japanese Patent Number 1-161993, to Ota; and Japanese Patent Number 2-262785, to Watanabe.
U.S. Pat. No. 5,067,019 to Juday et al., relates to a machine which accepts a real time video image in the form of a matrix of pixels and remaps such image, according to a selectable one of a plurality of mapping functions, to create an output matrix of pixels. For remapping input images from one coordinate system to another, a set of look-up tables is used for the data necessary to perform a particular transform. However, the look-up tables are not stored in compressed form, nor are they attached in compressed form to the image data.
U.S. Pat. No. 4,914,508, to Music et al., relates to a method and system for statistically encoding color video data. In this system, the color components in a picture frame are encoded, compressed and then stored in a look-up table. The LUT itself is not compressed, nor does the LUT consist of N to M-dimensional transform representative data which is compressed and made available to an image processing system in which the represented transform is to be applied. Furthermore, the LUTs described by Music et al., are not attached in compressed form to image data.
U.S. Pat. No. 4,797,729, to Tsai, describes systems and methods for compressing digitized color image signals in real time using a block truncation code. Again, only the data signal is compressed; not a transform representative LUT. Furthermore, there is no teaching of a compressed transform representative LUT being attached to image data for any purpose.
U.S. Pat. No. 4,941,038, to Walowit, which describes a method for processing color image data which converts input RGB color data to output CMY color data, using an intermediate color space; Japanese Patent Number 63-164574, to Kawamura, which relates to a decoding system which utilizes LUTs to decode encoded color image data; Japanese Patent Number 2-237269, to Murakami, which relates to a high efficiency compression recording display system for storing color pictures; Japanese Patent Number 1-51889, to Yamashita, which describes a video signal processor which utilizes data compression techniques; Japanese Patent Number 1-161993, to Ota, which relates to a coding system for color information; and Japanese Patent Number 2-262785, to Watanabe; all call for the use of data compression techniques and/or the use of look-up tables to process image data.
Once again, however, none of the aforementioned patents teach attaching compressed a N to M-dimensional transform representative LUT (or other compressed transform representative data structure) to image data for any purpose; much less teach the use of any type of image data file having a compressed transform representative data structure attached thereto.
As indicated in the incorporated patent application, beside being utilized to perform simple tonal re-mappings of monochrome imagery and conversions of color imagery from one color representation into some other representation (as indicated hereinabove), LUTs representing N to M-dimensional transforms can be used for color calibrating input and output devices and for generally converting image data from one representation to another whether color oriented or not.
For background purposes only, it should be noted that some of the more common functional color transforms are described by R. W. G. Hunt in a publication entitled "Measuring Colour", published by John Wiley and Sons, at pages 197-198, and by F. W. Billmeyer, Jr. and M. Saltzman, in a publication entitled "Principles of Color Technology", also published by John Wiley and Sons, at pages 81-110.
Although not constituting a part of the invention per se, methods for generating transform representative LUTs, together with several data compression techniques presently used for image processing purposes, will be briefly described herein for the sake of completeness.
Methods for generating multi-dimensional color calibration tables are well known to those skilled in the art as exemplified by H. J. Trussell in an article entitled "Application of Set Theoretic Methods To Color Systems", published in Color Research and Applications, Volume 16, No. 1, February, 1991, at pages 31-41; and by the teachings of W. F. Schreiber (in U.S. Pat. No. 4,500,919) and P. C. Pugsley (in U.S. Pat. No. 4,307,249).
According to these references, look-up tables may be generated using measured visual color responses from color patches with known device colors. The mapping of the visual color response to the device color to reproduce the color response at the output of a given device is then implemented with a look-up table.
As for data compression techniques per se, which are well known in the prior art to support a variety of image processing applications, such techniques may best be described (in general terms for background purposes only) as coupled processes consisting of a data transformation followed by quantization and encoding. The data transform pre-processes the data to effect a new, more compact data representation.
The pre-processed data can then, for example, be quantized, as taught by J. R. Sullivan in U.S. Pat. No. 4,885,636, and T. J. Lynch in the publication entitled "Data Compression Techniques and Applications", published by Van Nostrand Reinhold; and encoded using, for example, lossless encoding techniques (as taught by D. A. Huffman in an article entitled "A Method for the Construction of Minimum Redundancy Codes", published in the Proceedings of the IRE, Volume 40, at pages 1098-01101, and as taught by Lempel et al in an article entitled "A Universal Algorithm for Sequential Data Compression", published in the IEEE Transactions On Information Theory, Volume IT-23(3), at pages 337-343); arithmetic coding (as taught in an article entitled "Q-Coder" appearing in the IBM Journal of Research and Development, in Volume 32(6), at pages 715-840); or some other desired encoding algorithm.
As indicated hereinabove, with the exception of the teachings set forth in the incorporated patent application, the known data compression techniques, applied in the image processing context, have only been used to compress image data per se; not the transform representative LUTs which are stored for use in processing input image data in either compressed or uncompressed form.
It should be noted that well known compression methodologies, such as differential pulse code modulation (DPCM) and discrete cosine transform (DCT), may be readily extended to span the N to M-dimensional space described by the look-up tables. As an example, due to the correlated and smoothly varying nature of color transformation tables, predictive and interpolative techniques are attractive in transforming such look-up table data into a compact representation. However, alternate techniques may be used to produce the compact LUTs without departing from the spirit or scope of the invention.
Specific techniques which may be used to compress the transform representative LUTs include, for example, hierarchical, lossless, or lossy compression techniques, depending on the nature of the transform data.
Hierarchical methods would allow for multi-resolution reconstruction of the LUTs. Lossless techniques may be used for compressing calibration data that cannot incur any numerical loss. However, there are situations in which some numerical loss may be acceptable, such as where the transform data is inherently noisy or over specified in terms of visual precision of color differences. In these situations a lossy compression method may be most suitable for use, with the advantage of producing an increased compression ratio.
In view of the state of the art and other reasons set forth hereinabove, it would be desirable to provide methods and apparatus (image processing devices and systems), which are capable of selectively attaching to image data, compressed transform representative data (such as a compressed transform representative LUT), stored in memory available to an image processing device or system.
Once providing methods and apparatus for attaching stored compressed transform representative data to image data, it would clearly be desirable to provide methods and apparatus capable of using the product of the attachment process, namely image data with compressed transform representative data attached thereto.
In particular, it would be desirable to provide methods and apparatus which are capable of being able to utilize image data which has compressed transform representative data attached thereto, for image processing purposes such as, for example, device calibration and/or image data transformation functions.
Still further, it would be desirable to provide methods and apparatus which are capable of performing both the aforementioned attachment and utilization functions.
Further yet, it would be desirable to provide methods and apparatus which support the use of compressed transform representative data structures not resident in a given image processing device or system. So long as the target device is able to recognize that the image data being presented includes attached compressed transform representative data, all the target device would need to do (to be able to apply the desired transform), is detach and decompress the transform representative data sent with the image data, and apply the transform specified thereby.
By attaching compressed transform representative data to image data, there is the added flexibility of remotely processing image data (using the attached compressed transform representative data), without having to know the nature of the transform per se; just the encoding scheme used to compress the transform representative data.
The aforementioned desirable methods and apparatus not only offer memory savings possibilities in the devices and systems in which compressed transform representative data is used; but also would provide the flexibility of allowing one of many user specified transforms to be attached to image data by a first image processing device or system, to be used by some other image processing device or system.
Thus, for example, an input device (such as a scanner) may have a plurality of compressed color calibration tables stored in the device itself, each associated with one of a plurality of image rendering devices to which the image data may be sent. One of these tables may, in accordance with the teachings of the present invention, be user selected and attached to a scanned image based, for example, on the user's knowledge of the particular image rendering device to which the image data will be sent. The image rendering device may then decompress the calibration table attached to the image data and perform the intended device calibration function.